package SwordFingerOffer;

import java.util.*;

public class Q32_PrintTreeLevel2 {
    //从上到家打印二叉树 要求区分层
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        //diff
        Map<TreeNode,Integer> map = new HashMap<>();
        //队列迭代
        Queue<TreeNode> queue = new LinkedList<>();
        map.put(root,1);
        queue.add(root);
        TreeNode poll = null;
        List<Integer> ans = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        int curLevel = 1;
        while (!queue.isEmpty()){
            poll = queue.poll();
            //代表换层了 对上层做总结
            if (curLevel != map.get(poll)){
                res.add(ans);
                ans = new LinkedList<>();
                curLevel++;
            }
            //最后一层一直跑的这个，而没有机会跑res.add(ans); 所以要做收尾处理
            ans.add(poll.val);
            if (poll.left != null)
                queue.add(poll.left);
                map.put(poll.left,curLevel + 1);
            if (poll.right != null)
                queue.add(poll.right);
                map.put(poll.right,curLevel + 1);
        }
        //最后一层收尾
        res.add(ans);
        return res;
    }

    //来自解答区 不加map 更通用版的层序按行便利
    public List<List<Integer>> levelOrderNoMap(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Q32_PrintTreeLevel2  fun = new Q32_PrintTreeLevel2();
        System.out.println(fun.levelOrder(root));
    }
}
